

public class Sort {
    public void insertSort(int[] array){
        for(int i = 1; i < array.length; i++){
            int key = array[i];
            int j = i - 1;
            for(; j >= 0; j--){
                if(array[j] > key){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = key;
        }
    }
    public void insertSort2(int[] array){
        for(int i = 1; i < array.length; i++){
            int key = array[i];
            int j = i - 1;
            for(; j >= 0; j--){
                if(array[j] > key){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = key;
        }
    }
    public void insertSort3(int[] array){
        for(int i = 1; i < array.length; i++){
            int key = array[i];
            int j = i - 1;
            for(;j >= 0; j--){
                if(array[j] > key){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = key;
        }
    }
    public void insertSort4(int[] array){
        for(int i = 1; i < array.length; i++){
            int key = array[i];
            int j = i - 1;
            for(; j >= 0; j--){
                if(array[j] > key){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = key;
        }
    }
    public void shell(int[] array,int gap){
        for(int i = gap; i < array.length; i++){
            int key = array[i];
            int j = i - gap;
            for(; j >= 0; j -= gap){
                if(array[j] > key){
                    array[j + gap] = array[j];
                }else{
                    break;
                }
            }
            array[j + gap] = key;
        }
    }
    public void shellSort(int[] array){
        int gap = array.length;
        while(gap > 1){
            gap >>>= 1;
            shell(array, gap);
        }
        shell(array, gap);
    }
    public void shell2(int[] array, int gap){
        for(int i = gap; i < array.length; i++){
            int key = array[i];
            int j = i - gap;
            for(; j >= 0; j -= gap){
                if(array[j] > key){
                    array[j + gap] = array[j];
                }else{
                    break;
                }
            }
            array[j + gap] = key;
        }
    }
    public void shellSort2(int[] array){
        int gap = array.length;
        while(gap > 1){
            gap >>>= 1;
            shell2(array, gap);
        }
        shell2(array, gap);
    }
    public void chooseSort(int[] array){
        for(int i = 0; i < array.length; i++){
            for(int j = i + 1; j < array.length; j++){
                if(array[i] > array[j]){
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }
    public void bubbleSort(int[] array){
        for(int i = 0; i < array.length - 1; i++){
            for(int j = 0; j < array.length - i - 1; j++){
                if(array[j] > array[j + 1]){
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }
    }
    //逆序:O(n^2)
    //顺序:O(n)
    //稳定
    public void insertSort5(int[] array){
        for(int i = 1; i < array.length; i++){
            int key = array[i];
            int j = i - 1;
            for(; j >= 0; j--){
                if(array[j] > key){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = key;
        }
    }
    //时间:O(n^1.3 ~ n^1.4)
    public void shell3(int[] array, int gap){
        for(int i = gap; i < array.length; i++){
            int key = array[i];
            int j = i - gap;
            for(; j >= 0; j -= gap){
                if(array[j] > key){
                    array[j + gap] = array[j];
                }else{
                    break;
                }
            }
            array[j + gap] = key;
        }
    }
    public void shellSort3(int[] array){
        int gap = array.length;
        while(gap > 1){
            gap >>>= 1;
            shell3(array, gap);
        }
        shell(array, 1);
    }
    //时间:O(n^2)无论怎样
    //不稳定
    public void chooseSort2(int[] array){
        for(int i = 0; i < array.length; i++){
            for(int j = i + 1; j < array.length; j++){
                if(array[i] > array[j]){
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }
    //时间O(n^2)逆序
    //顺序o(n)
    //稳定
    public void bubbleSort2(int[] array){
        for(int i = 0; i < array.length - 1; i++){
            boolean flag = false;
            for(int j = 0; j < array.length - 1 - i; j++){
                if(array[j] > array[j + 1]){
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    flag = true;
                }
            }
            if(!flag){
                break;
            }
        }
    }
    //堆排序
    public void heapSort(int[] array){
        createBigHeap(array);
        int end = array.length - 1;
        while(end > 0){
            swap(array, 0, end);
            adjustDown(array, 0, end);
            end--;
        }
    }
    //建立大根堆
    public void createBigHeap(int[] array){
        int len = array.length;
        for(int parent = (len - 1 - 1) / 2; parent >= 0; parent--){
            adjustDown(array, parent, len);
        }
    }
    //向下调整
    public void adjustDown(int[] array, int parent, int len){
        int child = parent * 2 + 1;
        while(child < len){
            //首先要有右孩子
            if(child + 1 < len && array[child] < array[child + 1]){
                child++;
            }
            if(array[child] > array[parent]){
                swap(array, child, parent);
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }
    public void swap(int[] array, int i, int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}
